#include "leveldb/slice.h"
#include "bloom_filter_hash.h"
#include "bloom_filter.h"

#define TEST_BIT(bits, offset)  ((bits[(offset) / 8]) & (0x01 << ((offset) & 0xFF)))
#define SET_BIT(bits, offset) (bits[(offset) / 8] |= 0x01 << ((offset) & 0xFF))

namespace leveldb {

 

uint32_t ElfHash(const Slice& key) {
	uint32_t hash = 0;
	uint32_t x	= 0;

	size_t size = key.size();			
	for (size_t i = 0; i < size; ++i) {
		hash = (hash << 4) + key[i];
		if ((x = hash & 0xF0000000L) != 0) {
			hash ^= (x >> 24);
			hash &= ~x;
		}
	}
	return (hash & 0x7FFFFFFF);
}

uint32_t BKDRHash(const Slice& key) {
	uint32_t seed = 13131; 
	uint32_t hash = 0;

	size_t size = key.size();			
	for (size_t i = 0; i < size; ++i) {
		hash = hash * seed + key[i];
	}
	return (hash & 0x7FFFFFFF);
}

uint32_t APHash(const Slice& key) {
	uint32_t hash = 0;

	size_t size = key.size();			
	for (size_t i = 0; i < size; ++i) {
		if ((i & 1) == 0) {
			hash ^= ((hash << 7) ^ key[i] ^ (hash >> 3));
		} else {
			hash ^= (~((hash << 11) ^ key[i] ^ (hash >> 5)));
		}
	}
	return (hash & 0x7FFFFFFF);
}

BloomFilterHash::BloomFilterHash() : kHashCount(3) {
	functions = new HashFunction[kHashCount];
	functions[0] = ElfHash;
	functions[1] = BKDRHash;
	functions[2] = APHash;
}

BloomFilterHash::~BloomFilterHash() {
	delete functions;
}



void BloomFilterHash::SetBits(const BloomFilterHash& handle, char* bits, size_t len, const Slice& key) {
	assert(bits != NULL);
	assert(len > 0);

	size_t max_bits_len = len * 8;
	for (size_t i = 0; i < handle.kHashCount; ++i) {
		size_t offset= (*handle.functions[i])(key) % max_bits_len;
		SET_BIT(bits, offset);
	}
}


bool BloomFilterHash::MaybeExist(const BloomFilterHash& handle, const char* bits, size_t len, const Slice& key) {
	assert(bits != NULL);
	assert(len > 0);

	size_t max_bits_len = len * 8;
	for (size_t i = 0; i < handle.kHashCount; ++i) {
		size_t offset= (*handle.functions[i])(key) % max_bits_len;
		if (TEST_BIT(bits, offset) == 0) {
			return false;
		}
	}
	return true;
}

}

